home *** CD-ROM | disk | FTP | other *** search
/ Language/OS - Multiplatform Resource Library / LANGUAGE OS.iso / cpp_libs / intrvews / xgrab.lha / xgrab / ui / OGC / alloc.c next >
Encoding:
C/C++ Source or Header  |  1990-03-06  |  23.2 KB  |  838 lines
  1. /**
  2.    GRAB Graph Layout and Browser System
  3.  
  4.    Copyright (c) 1989, Tera Computer Company
  5.  **/
  6.  
  7. /*
  8.  * This file contains the functions:
  9.  *    void new_hblk(n)
  10.  *    static void clear_marks()
  11.  *    tl_mark(p)
  12.  *    mark()
  13.  *    mark_all(b,t)
  14.  *    void gcollect()
  15.  *    expand_hp: func[val Short] val Void
  16.  *    struct obj * _allocobj(sz)
  17.  *    struct obj * _allocaobj(sz)
  18.  *
  19.  * And the global variables:
  20.  *    struct obj * objfreelist[MAXOBJSZ+1];
  21.  *    struct obj * aobjfreelist[MAXOBJSZ+1];
  22.  *    word * mark_stack_bottom;
  23.  *    word * mark_stack_top;
  24.  */
  25.  
  26.  
  27. # include <stdio.h>
  28. # include <signal.h>
  29. # include <sys/types.h>
  30. # include <sys/times.h>
  31. # include "runtime.h"
  32.  
  33. /* Leaving these defined enables output to stderr.  In order of */
  34. /* increasing verbosity:                                        */
  35. #define REPORT_FAILURE   /* Print values that looked "almost" like pointers */
  36. #undef REPORT_FAILURE
  37. #define DEBUG            /* Verbose debugging output */
  38. #undef DEBUG
  39. #define DEBUG2           /* EXTREMELY verbose debugging output */
  40. #undef DEBUG2
  41. #define USE_STACK       /* Put mark stack onto process stack.  This assumes */
  42.             /* that it's safe to put data below the stack ptr,  */
  43.             /* and that the system will expand the stack as     */
  44.             /* necessary.  This is known to be true under Sun   */
  45.             /* UNIX (tm) and Vax Berkeley UNIX.  It is also     */
  46.             /* known to be false under some other UNIX          */
  47.             /* implementations.                                 */
  48. #undef USE_HEAP
  49. /*
  50.  * This is an attempt at a garbage collecting storage allocator
  51.  * on a Motorola 68000 series or an a Vax.  The garbage
  52.  * collector is overly conservative in that it may fail to reclaim
  53.  * inaccessible storage.  On the other hand, it does not assume
  54.  * any runtime tag information.
  55.  * We make the following assumptions:
  56.  *  1.  We are running on a 68000, 68008, 68010 or 68020 based machine
  57.  *      or on a Vax, under a 4.2 BSD like version of UNIX.
  58.  *  2.  For every accessible object, a pointer to it is stored in
  59.  *          a) the stack segment, or
  60.  *          b) the data or bss segment, or
  61.  *          c) the registers, or
  62.  *          d) an accessible block.
  63.  *
  64.  */
  65.  
  66. /*
  67.  * Separate free lists are maintained for different sized objects.
  68.  * The lists objfreelist[i] contain free objects of size i which may
  69.  * contain nested pointers.  The lists aobjfreelist[i] contain free
  70.  * atomic objects, which may not contain nested pointers.
  71.  * The call allocobj(i) insures that objfreelist[i] points to a non-empty
  72.  * free list it returns a pointer to the first entry on the free list.
  73.  * Allocobj may be called from C to allocate an object of size i
  74.  * as follows:
  75.  *
  76.  *            opp = &(objfreelist[i]);
  77.  *            if (*opp == (struct obj *)0) allocobj(i);
  78.  *            ptr = *opp;
  79.  *            *opp = ptr->next;
  80.  *
  81.  * Note that this is very fast if the free list is non-empty; it should
  82.  * only involve the execution of 4 or 5 simple instructions.
  83.  * All composite objects on freelists are cleared, except for
  84.  * their first longword.
  85.  */
  86.  
  87. /*
  88.  *  The allocator uses allochblk to allocate large chunks of objects.
  89.  * These chunks all start on addresses which are multiples of
  90.  * HBLKSZ.  All starting addresses are maintained on a contiguous
  91.  * list so that they can be traversed in the sweep phase of garbage collection.
  92.  * This makes it possible to check quickly whether an
  93.  * arbitrary address corresponds to an object administered by the
  94.  * allocator.
  95.  *  We make the (probably false) claim that this can be interrupted
  96.  * by a signal with at most the loss of some chunk of memory.
  97.  */
  98.  
  99. /* Declarations for fundamental data structures.  These are grouped */
  100. /* in a single structure, so that the collector can skip over them. */
  101.  
  102. struct __gc_arrays _gc_arrays;
  103.  
  104. long heapsize = 0;      /* Heap size in bytes */
  105.  
  106. long non_gc_bytes = 0;  /* Number of bytes not intended to be collected */
  107.  
  108. /*
  109.  * Allocate a new heapblock for objects of size n.
  110.  * Add all of the heapblock's objects to the free list for objects
  111.  * of that size.  A negative n requests atomic objects.
  112.  */
  113. void new_hblk(n)
  114. long n;
  115. {
  116.     register word *p,
  117.           *r;
  118.     word *last_object;        /* points to last object in new hblk    */
  119.     register struct hblk *h;    /* the new heap block            */
  120.     register long abs_sz;    /* |n|    */
  121.     register int i;
  122.  
  123. #   ifdef PRINTSTATS
  124.     if ((sizeof (struct hblk)) > HBLKSIZE) {
  125.         abort("HBLK SZ inconsistency");
  126.         }
  127. #   endif
  128.  
  129.   /* Allocate a new heap block */
  130.     h = allochblk(n);
  131.  
  132.   /* Add it to hblklist */
  133.     add_hblklist(h);
  134.  
  135.   /* Add objects to free list */
  136.     abs_sz = abs(n);
  137.     p = &(h -> hb_body[abs_sz]);    /* second object in *h    */
  138.     r = &(h -> hb_body[0]);           /* One object behind p    */
  139.     last_object = ((word *)((char *)h + HBLKSIZE)) - abs_sz;
  140.                 /* Last place for last object to start */
  141.  
  142.   /* make a list of all objects in *h with head as last object */
  143.     while (p <= last_object) {
  144.       /* current object's link points to last object */
  145.     ((struct obj *)p) -> obj_link = (struct obj *)r;
  146.     r = p;
  147.     p += abs_sz;
  148.     }
  149.     p -= abs_sz;            /* p now points to last object */
  150.  
  151.   /*
  152.    * put p (which is now head of list of objects in *h) as first
  153.    * pointer in the appropriate free list for this size.
  154.    */
  155.     if (n < 0) {
  156.     ((struct obj *)(h -> hb_body)) -> obj_link = aobjfreelist[abs_sz];
  157.     aobjfreelist[abs_sz] = ((struct obj *)p);
  158.     } else {
  159.     ((struct obj *)(h -> hb_body)) -> obj_link = objfreelist[abs_sz];
  160.     objfreelist[abs_sz] = ((struct obj *)p);
  161.     }
  162.  
  163.   /*
  164.    * Set up mask in header to facilitate alignment checks
  165.    * See "runtime.h" for a description of how this works.
  166.    */
  167.     switch (abs_sz) {
  168.         case 1:
  169.         h -> hb_mask = 0x3;
  170.         break;
  171.         case 2:
  172.         h -> hb_mask = 0x7;
  173.         break;
  174.         case 4:
  175.         h -> hb_mask = 0xf;
  176.         break;
  177.         case 8:
  178.         h -> hb_mask = 0x1f;
  179.         break;
  180.         case 16:
  181.         h -> hb_mask = 0x3f;
  182.         break;
  183.         /* By default it remains set to a negative value */
  184.     }
  185.  
  186. #   ifdef DEBUG
  187.     printf("Allocated new heap block at address 0x%X\n",
  188.         h);
  189. #   endif
  190. }
  191.  
  192.  
  193. /* some more variables */
  194.  
  195. extern long mem_found;  /* Number of reclaimed longwords */
  196.             /* after garbage collection      */
  197.  
  198. extern long atomic_in_use, composite_in_use;
  199. extern errno;
  200.  
  201. /*
  202.  * Clear mark bits in all allocated heap blocks
  203.  */
  204. static void clear_marks()
  205. {
  206.     register int j;
  207.     register struct hblk **p;
  208.     register struct hblk *q;
  209.  
  210.     for (p = hblklist; p < last_hblk; p++) {
  211.     q = *p;
  212.         for (j = 0; j < MARK_BITS_SZ; j++) {
  213.         q -> hb_marks[j] = 0;
  214.         }
  215.     }
  216. }
  217.  
  218. /* Limits of stack for mark routine.  Set by caller to mark.           */
  219. /* All items between mark_stack_top and mark_stack_bottom-1 still need */
  220. /* to be marked.  All items on the stack satisfy quicktest.  They do   */
  221. /* not necessarily reference real objects.                             */
  222. word * mark_stack_bottom;
  223. word * mark_stack_top;
  224.  
  225. #ifdef USE_STACK
  226. # define STACKGAP 512 /* Gap in longwords between hardware stack and    */
  227.               /* the mark stack.                */
  228. #endif
  229.  
  230. /* Top level mark routine */
  231. tl_mark(p)
  232. word * p;
  233. {
  234.     if (quicktest(p)) {
  235.     /* Allocate mark stack, leaving a hole below the real stack. */
  236. #         ifdef USE_STACK
  237. #        ifdef M68K
  238.           asm("movl a7,_mark_stack_bottom");/* _mark_stack_bottom := SP */
  239. #        else
  240. #          ifdef VAX
  241.            asm("movl sp,_mark_stack_bottom");/* _mark_stack_bottom := SP */
  242. #             else
  243. #               ifdef I386
  244.           asm("movl %esp,_mark_stack_bottom");
  245.                          /* _mark_stack_bottom := SP */
  246. #               else
  247.            --> fix it
  248. #               endif
  249. #          endif
  250. #        endif
  251.         mark_stack_bottom -= STACKGAP;
  252.         mark_stack_top = mark_stack_bottom - 1;
  253. #         else
  254. #               ifdef SPARC
  255.           -> fix it <-
  256. #               else
  257. #               endif
  258. #         endif
  259.       * mark_stack_top = (word) p;
  260.  
  261. #         ifdef DEBUG2
  262.         printf("Tl_mark found plausible pointer: %X\n", p);
  263. #         endif
  264.  
  265.     /* and now mark the one element on the stack */
  266.       mark();
  267.     }
  268. }
  269.  
  270. #ifdef USE_STACK
  271. #   define PUSH_MS(ptr) *(--mark_stack_top) = (word) ptr
  272. #   define NOT_DONE(a,b) (a < b)
  273. #else
  274. # ifdef USE_HEAP
  275.     char *cur_break=0;
  276. #   define STACKINCR (char *) 0x1000
  277. #   define PUSH_MS(ptr)                         \
  278.     if (cur_break == 0) cur_break = (char *) sbrk(0);        \
  279.     mark_stack_top++;                        \
  280.     if ((char*)mark_stack_top >= cur_break) {             \
  281.         if (sbrk(STACKINCR) == -1) {                \
  282.         printf("sbrk didn't work, code = %d\n",errno);  \
  283.         exit(1);                        \
  284.         } else {                            \
  285.         cur_break = (char *) sbrk(0);                \
  286.         }                                \
  287.     }                                \
  288.     *mark_stack_top = (word) ptr
  289. #   define NOT_DONE(a,b) (a > b)
  290. # else
  291.     --> fixit <--
  292. # endif
  293. #endif
  294.  
  295. mark()
  296. {
  297.   register long sz;
  298.   extern char end, etext;
  299.   register struct obj *p; /* pointer to current object to be marked */
  300.  
  301.   while (NOT_DONE(mark_stack_top,mark_stack_bottom)) {
  302.       register long word_no;
  303.       register long mask;
  304.       register struct hblk * h;
  305.  
  306. #    ifdef USE_STACK
  307.       p = (struct obj *)(*mark_stack_top++);
  308. #    else
  309. #     ifdef USE_HEAP
  310.     p = (struct obj *)(*mark_stack_top--);
  311. #     else
  312.     --> fixit <--
  313. #     endif
  314. #    endif
  315.  
  316.   /* if not a pointer to obj on heap, skip it */
  317.     if (((char *) p) >= heaplim) {
  318.     continue;
  319.     }
  320.  
  321.     h = HBLKPTR(p);
  322.     word_no = ((word *)p) - ((word *)h);
  323.  
  324.   /* Check mark bit first, since this test is much more likely to */
  325.   /* fail than later ones.                                        */
  326.     if (mark_bit(h, word_no)) {
  327.     continue;
  328.     }
  329.  
  330.     if (!is_hblk(h)) {
  331. #    ifdef REPORT_FAILURE
  332.         if (quicktest(p)) {
  333.         printf("-> Pointer to non-heap loc: %X\n", p);
  334.         }
  335. #       endif
  336.     continue;
  337.     }
  338.     sz = HB_SIZE(h);
  339.     mask = h -> hb_mask;
  340.     if (!is_proper_obj(p,h,sz,mask)||((word *)p) + sz > (word *)heaplim) {
  341.       /* 
  342.        * Note that we dont check for pointers to the block header.
  343.        * This doesn't cause any problems, since we have mark
  344.        * bits allocated for such bogus objects.
  345.        * The same holds for pointers past the last object
  346.        * (unless reference would cause an exception)
  347.        */
  348. #    ifdef REPORT_FAILURE
  349.         printf("-> Bad pointer to heap block: %X,sz = %d\n",p,sz);
  350. #    endif
  351.     continue;
  352.     }
  353.  
  354. #   ifdef DEBUG2
  355.     printf("*** set bit for heap %x, word %x\n",h,word_no);
  356. #   endif
  357.     set_mark_bit(h, word_no);
  358.     if (h -> hb_sz < 0) {
  359.     /* Atomic object */
  360.       continue;
  361.     }
  362.     {
  363.       /* Mark from fields inside the object */
  364.     register struct obj ** q;
  365.     register struct obj * r;
  366.     register long lim;   /* Should be struct obj **, but we're out of */
  367.                  /* A registers on a 68000.                   */
  368.  
  369. #       ifdef UNALIGNED
  370.       lim = ((long)(&(p -> obj_component[sz]))) - 3;
  371. #       else
  372.       lim = (long)(&(p -> obj_component[sz]));
  373. #       endif
  374.     for (q = (struct obj **)(&(p -> obj_component[0]));
  375.                     q < (struct obj **)lim;) {
  376.         r = *q;
  377.         if (quicktest(r)) {
  378. #               ifdef DEBUG2
  379.             printf("Found plausible nested pointer");
  380.             printf(": 0x%X inside 0x%X at 0x%X\n", r, p, q);
  381. #               endif
  382.         PUSH_MS(((word)r));
  383.         }
  384. #           ifdef UNALIGNED
  385.         q = ((struct obj **)(((long)q)+ALIGNMENT));
  386. #           else
  387.         q++;
  388. #           endif 
  389.     }
  390.     }
  391.   }
  392. }
  393.  
  394.  
  395. /*********************************************************************/
  396. /* Mark all locations reachable via pointers located between b and t */
  397. /*********************************************************************/
  398. mark_all(b, t)
  399. word * b;
  400. word * t;
  401. {
  402.     register word *p;
  403.     register word r;
  404.     register word *lim;
  405.  
  406. #   ifdef DEBUG
  407.     printf("Checking for pointers between 0x%X and 0x%X\n",
  408.         b, t);
  409. #   endif
  410.  
  411.     /* Allocate mark stack, leaving a hole below the real stack. */
  412. #   ifdef USE_STACK
  413. #    ifdef M68K
  414.         asm("movl a7,_mark_stack_bottom");    /* mark_stack_bottom := SP */
  415. #    else
  416. #      ifdef VAX
  417.         asm("movl sp,_mark_stack_bottom");    /* mark_stack_bottom := SP */
  418. #         else
  419. #           ifdef SPARC
  420.           asm(" mov %sp,%o0");
  421.           put_mark_stack_bottom();
  422. #           else
  423. #             ifdef I386
  424.         asm("movl %esp,_mark_stack_bottom");
  425.                          /* _mark_stack_bottom := SP */
  426. #             else
  427.            --> fix it
  428. #             endif
  429. #           endif
  430. #      endif
  431. #    endif
  432.     mark_stack_bottom -= STACKGAP;     /* r1 - STACKGAP    */
  433.     mark_stack_top = mark_stack_bottom;
  434. #   else
  435. #     ifdef USE_HEAP
  436.     mark_stack_bottom = (word *) sbrk(0); /* current break */
  437.     mark_stack_top = mark_stack_bottom;
  438. #     else
  439.       -> then where should the mark stack go ? <-
  440. #     endif
  441. #   endif
  442.  
  443.   /* Round b down so it is properly aligned */
  444. #   if (ALIGNMENT == 2)
  445.       b = (word *)(((long) b) & ~1);
  446. #   else
  447. #     if (ALIGNMENT == 4 || !defined(UNALIGNED))
  448.     b = (word *)(((long) b) & ~3);
  449. #     endif
  450. #   endif
  451.  
  452.   /* check all pointers in range and put on mark_stack if quicktest true */
  453.     lim = t - 1 /* longword */;
  454.     for (p = b; ((unsigned) p) <= ((unsigned) lim);) {
  455.         /* Coercion to unsigned in the preceding appears to be necessary */
  456.         /* due to a bug in the VAX C compiler.                           */
  457.     r = *p;
  458.     if (quicktest(r)) {
  459. #           ifdef DEBUG2
  460.         printf("Found plausible pointer: %X\n", r);
  461. #           endif
  462.         PUSH_MS(r);         /* push r onto the mark stack */
  463.     }
  464. #       ifdef UNALIGNED
  465.       p = (word *)(((char *)p) + ALIGNMENT);
  466. #       else
  467.       p++;
  468. #       endif
  469.     }
  470.     if (mark_stack_top != mark_stack_bottom) mark();
  471.  
  472. #   ifdef USE_HEAP
  473.       brk(mark_stack_bottom);     /* reset break to where it was before */
  474.       cur_break = (char *) mark_stack_bottom;
  475. #   endif
  476. }
  477.  
  478. /*
  479.  * Restore inaccessible objects to the free list 
  480.  * update mem_found (number of reclaimed longwords after garbage collection)
  481.  */
  482. void gcollect()
  483. {
  484.     register long TMP_SP; /* must be bound to r11 on VAX or RT, d7 on M68K */
  485.  
  486.     extern int holdsigs();  /* disables non-urgent signals - see the    */
  487.                 /* file "callcc.c"                */
  488.  
  489.     long Omask;        /* mask to restore signal mask to after
  490.              * critical section.  This variable is assumed
  491.              * to be the first variable on the stack frame
  492.              * and to be longword aligned.
  493.              */
  494.  
  495. #   ifdef PRINTTIMES
  496.       /* some debugging values */
  497.     double start_time;
  498.     double mark_time;
  499.     double done_time;
  500.     struct tms time_buf;
  501. #       define FTIME \
  502.          (((double)(time_buf.tms_utime + time_buf.tms_stime))/60.0)
  503.  
  504.       /* Get starting time */
  505.         times(&time_buf);
  506.         start_time = FTIME;
  507. #   endif
  508.  
  509. #   ifdef DEBUG2
  510.     printf("Here we are in gcollect\n"); 
  511. #   endif
  512.  
  513.     /* Don't want to deal with signals in the middle so mask 'em out */
  514.     Omask = holdsigs();
  515.  
  516.     /*
  517.      * mark from registers - i.e., call tl_mark(i) for each
  518.      * register i
  519.      */
  520. #       ifdef VAX
  521.       /* r1 through r5 are preserved by allocobj, and therefore     */
  522.       /* on the stack.                                              */
  523.       /* We could do this for the other registers, too ...          */
  524.       asm("pushl r11");     asm("calls $1,_tl_mark");
  525.       asm("pushl r10");     asm("calls $1,_tl_mark");
  526.       asm("pushl r9");    asm("calls $1,_tl_mark");
  527.       asm("pushl r8");    asm("calls $1,_tl_mark");
  528.       asm("pushl r7");    asm("calls $1,_tl_mark");
  529.       asm("pushl r6");    asm("calls $1,_tl_mark");
  530.  
  531.       asm("movl sp,r11");        /* TMP_SP = stack pointer sp    */
  532. #       endif
  533. #       ifdef M68K
  534.       /* a0, a1 and d1 are preserved by allocobj */
  535.       /*  and therefore are on stack             */
  536.     
  537.       asm("subqw #0x4,sp");        /* allocate word on top of stack */
  538.  
  539.       asm("movl a0,sp@");    asm("jbsr _tl_mark");
  540.       asm("movl a1,sp@");    asm("jbsr _tl_mark");
  541.       asm("movl a2,sp@");    asm("jbsr _tl_mark");
  542.       asm("movl a3,sp@");    asm("jbsr _tl_mark");
  543.       asm("movl a4,sp@");    asm("jbsr _tl_mark");
  544.       asm("movl a5,sp@");    asm("jbsr _tl_mark");
  545.       /* Skip frame pointer and stack pointer */
  546.       asm("movl d0,sp@");    asm("jbsr _tl_mark");
  547.       asm("movl d1,sp@");    asm("jbsr _tl_mark");
  548.       asm("movl d2,sp@");    asm("jbsr _tl_mark");
  549.       asm("movl d3,sp@");    asm("jbsr _tl_mark");
  550.       asm("movl d4,sp@");    asm("jbsr _tl_mark");
  551.       asm("movl d5,sp@");    asm("jbsr _tl_mark");
  552.       asm("movl d6,sp@");    asm("jbsr _tl_mark");
  553.       asm("movl d7,sp@");    asm("jbsr _tl_mark");
  554.  
  555.       asm("addqw #0x4,sp");        /* put stack back where it was    */
  556.  
  557.       asm("movl a7,d7");        /* TMP_SP = stack pointer a7    */
  558. #       endif
  559.  
  560. #       ifdef I386
  561.       asm("pushl %eax");  asm("call _tl_mark"); asm("addl $4,%esp");
  562.       asm("pushl %ecx");  asm("call _tl_mark"); asm("addl $4,%esp");
  563.       asm("pushl %edx");  asm("call _tl_mark"); asm("addl $4,%esp");
  564.       asm("pushl %esi");  asm("call _tl_mark"); asm("addl $4,%esp");
  565.       asm("pushl %edi");  asm("call _tl_mark"); asm("addl $4,%esp");
  566.       asm("pushl %ebx");  asm("call _tl_mark"); asm("addl $4,%esp");
  567. #       endif
  568.  
  569. #       ifdef SPARC
  570.       save_regs_in_stack();
  571. #       endif
  572.  
  573.  
  574.       /* other machines... */
  575. #       if !(defined M68K) && !(defined VAX) && !(defined SPARC) && !(defined I386)
  576.         --> bad news <--
  577. #       endif
  578.  
  579. #       ifdef DEBUG
  580.         printf("done marking from regs - calling mark_all\n");
  581. #    endif
  582.  
  583.       /* put stack pointer into TMP_SP               */
  584.       /* and mark everything on the stack.           */
  585.     /* A hack */
  586.     TMP_SP = ((long)(&Omask));
  587.     mark_all( TMP_SP, STACKTOP );
  588.  
  589.  
  590.     /* Mark everything in data and bss segments.                             */
  591.     /* Skip gc data structures. (It's OK to mark these, but it wastes time.) */
  592.     {
  593.         extern char etext, end;
  594.  
  595.             mark_all(DATASTART, begin_gc_arrays);
  596.             mark_all(end_gc_arrays, &end);
  597.     }
  598.  
  599.     /* Clear free list mark bits, in case they got accidentally marked   */
  600.     /* Note: HBLKPTR(p) == pointer to head of block containing *p        */
  601.     /* Also subtract memory remaining from mem_found count.              */
  602.     /* Note that composite objects on free list are cleared.             */
  603.     /* Thus accidentally marking a free list is not a problem;  only     */
  604.     /* objects on the list itself will be marked, and that's fixed here. */
  605.       {
  606.     register int size;        /* current object size        */
  607.     register struct obj * p;    /* pointer to current object    */
  608.     register struct hblk * q;    /* pointer to block containing *p */
  609.     register int word_no;           /* "index" of *p in *q          */
  610. #       ifdef REPORT_FAILURE
  611.         int prev_failure = 0;
  612. #       endif
  613.  
  614.     for (size = 1; size < MAXOBJSZ; size++) {
  615.         for (p= objfreelist[size]; p != ((struct obj *)0); p=p->obj_link){
  616.         q = HBLKPTR(p);
  617.         word_no = (((word *)p) - ((word *)q));
  618. #               ifdef REPORT_FAILURE
  619.           if (!prev_failure && mark_bit(q, word_no)) {
  620.             printf("-> Pointer to composite free list: %X,sz = %d\n",
  621.                 p, size);
  622.             prev_failure = 1;
  623.           }
  624. #               endif
  625.         clear_mark_bit(q, word_no);
  626.         mem_found -= size;
  627.         }
  628. #           ifdef REPORT_FAILURE
  629.         prev_failure = 0;
  630. #           endif
  631.     }
  632.     for (size = 1; size < MAXAOBJSZ; size++) {
  633.         for(p= aobjfreelist[size]; p != ((struct obj *)0); p=p->obj_link){
  634.         q = HBLKPTR(p);
  635.         word_no = (((long *)p) - ((long *)q));
  636. #               ifdef REPORT_FAILURE
  637.           if (!prev_failure && mark_bit(q, word_no)) {
  638.             printf("-> Pointer to atomic free list: %X,sz = %d\n",
  639.                 p, size);
  640.             prev_failure = 1;
  641.           }
  642. #               endif
  643.         clear_mark_bit(q, word_no);
  644.         mem_found -= size;
  645.         }
  646. #           ifdef REPORT_FAILURE
  647.         prev_failure = 0;
  648. #           endif
  649.     }
  650.       }
  651.  
  652. #   ifdef PRINTTIMES
  653.       /* Get intermediate time */
  654.     times(&time_buf);
  655.     mark_time = FTIME;
  656. #   endif
  657.  
  658. #   ifdef PRINTSTATS
  659.     printf("Bytes recovered before reclaim - f.l. count = %d\n",
  660.            WORDS_TO_BYTES(mem_found));
  661. #   endif
  662.  
  663.   /* Reconstruct free lists to contain everything not marked */
  664.     reclaim();
  665.  
  666.   /* clear mark bits in all allocated heap blocks */
  667.     clear_marks();
  668.  
  669. #   ifdef PRINTSTATS
  670.     printf("Reclaimed %d bytes in heap of size %d bytes\n",
  671.            WORDS_TO_BYTES(mem_found), heapsize);
  672.     printf("%d (atomic) + %d (composite) bytes in use\n",
  673.            WORDS_TO_BYTES(atomic_in_use),
  674.            WORDS_TO_BYTES(composite_in_use));
  675. #   endif
  676.  
  677.   /*
  678.    * What follows is somewhat heuristic.  Constant may benefit
  679.    * from tuning ...
  680.    */
  681.     if (WORDS_TO_BYTES(mem_found) * 4 < heapsize) {
  682.       /* Less than about 1/4 of available memory was reclaimed - get more */
  683.     {
  684.         long size_to_get = HBLKSIZE + hincr * HBLKSIZE;
  685.         struct hblk * thishbp;
  686.         char * nheaplim;
  687.  
  688.         thishbp = HBLKPTR(((unsigned)sbrk(0))+HBLKSIZE-1 );
  689.         nheaplim = (char *) (((unsigned)thishbp) + size_to_get);
  690.         if( ((char *) brk(nheaplim)) == ((char *)-1) ) {
  691.         write(2,"Out of memory, trying to continue ...\n",38);
  692.         } else {
  693.         heaplim = nheaplim;
  694.         thishbp->hb_sz = 
  695.             BYTES_TO_WORDS(size_to_get - sizeof(struct hblkhdr));
  696.         freehblk(thishbp);
  697.         heapsize += size_to_get;
  698.         update_hincr;
  699.         }
  700. #           ifdef PRINTSTATS
  701.         printf("Gcollect: needed to increase heap size by %d\n",
  702.                size_to_get);
  703. #           endif
  704.     }
  705.     }
  706.  
  707.    /* Reset mem_found for next collection */
  708.      mem_found = 0;
  709.  
  710.   /* Reenable signals */
  711.     sigsetmask(Omask);
  712.  
  713.   /* Get final time */
  714. #   ifdef PRINTTIMES
  715.     times(&time_buf);
  716.     done_time = FTIME;
  717.     printf("Garbage collection took %7.2f + %7.2f secs\n",
  718.            mark_time - start_time, done_time - mark_time);
  719. #   endif
  720. }
  721.  
  722. /*
  723.  * this is a function callable from Russell to explicity make the heap
  724.  * bigger for use by programs which know they'll need a bigger heap than
  725.  * the default.
  726.  */
  727. void expand_hp(n)
  728. int n;
  729. {
  730.     struct hblk * thishbp = HBLKPTR(((unsigned)sbrk(0))+HBLKSIZE-1 );
  731.     extern int holdsigs();
  732.     int Omask;
  733.  
  734.     /* Don't want to deal with signals in the middle of this */
  735.     Omask = holdsigs();
  736.  
  737.     heaplim = (char *) (((unsigned)thishbp) + n * HBLKSIZE);
  738.     if (n > 2*hincr) {
  739.     hincr = n/2;
  740.     }
  741.     if( ((char *) brk(heaplim)) == ((char *)-1) ) {
  742.     write(2,"Out of Memory!\n",15);
  743.     exit(-1);
  744.     }
  745. #   ifdef PRINTSTATS
  746.      if(heapsize)
  747.     printf("Voluntarily increasing heap size by %d\n",
  748.            n*HBLKSIZE);
  749. #   endif
  750.     thishbp->hb_sz = BYTES_TO_WORDS(n * HBLKSIZE - sizeof(struct hblkhdr));
  751.     freehblk(thishbp);
  752.     heapsize += ((char *)heaplim) - ((char *)thishbp);
  753.     /* Reenable signals */
  754.     sigsetmask(Omask);
  755. }
  756.  
  757.  
  758. extern int dont_gc;  /* Unsafe to start garbage collection */
  759.  
  760. /*
  761.  * Make sure the composite object free list for sz is not empty.
  762.  * Return a pointer to the first object on the free list.
  763.  * The object MUST BE REMOVED FROM THE FREE LIST BY THE CALLER.
  764.  *
  765.  * note: _allocobj
  766.  */
  767. struct obj * _allocobj(sz)
  768. long sz;
  769. {
  770.     if (sz == 0) return((struct obj *)0);
  771.  
  772. #   ifdef DEBUG2
  773.     printf("here we are in _allocobj\n");
  774. #   endif
  775.  
  776.     if (objfreelist[sz] == ((struct obj *)0)) {
  777.       if (hblkfreelist == ((struct hblk *)0) && !dont_gc) {
  778.     if (GC_DIV * non_gc_bytes < GC_MULT * heapsize) {
  779. #         ifdef DEBUG
  780.         printf("Calling gcollect\n");
  781. #         endif
  782.       gcollect();
  783.     } else {
  784.       expand_hp(NON_GC_HINCR);
  785.     }
  786.       }
  787.       if (objfreelist[sz] == ((struct obj *)0)) {
  788. #       ifdef DEBUG
  789.         printf("Calling new_hblk\n");
  790. #    endif
  791.       new_hblk(sz);
  792.       }
  793.     }
  794. #   ifdef DEBUG2
  795.     printf("Returning %x from _allocobj\n",objfreelist[sz]);
  796.     printf("Objfreelist[%d] = %x\n",sz,objfreelist[sz]);
  797. #   endif
  798.     return(objfreelist[sz]);
  799. }
  800.  
  801. /*
  802.  * Make sure the atomic object free list for sz is not empty.
  803.  * Return a pointer to the first object on the free list.
  804.  * The object MUST BE REMOVED FROM THE FREE LIST BY THE CALLER.
  805.  *
  806.  * note: this is called by allocaobj (see the file allocobj.s)
  807.  */
  808. struct obj * _allocaobj(sz)
  809. long sz;
  810. {
  811.     if (sz == 0) return((struct obj *)0);
  812.  
  813.     if (aobjfreelist[sz] == ((struct obj *) 0)) {
  814.       if (hblkfreelist == ((struct hblk *)0) && !dont_gc) {
  815.     if (GC_DIV * non_gc_bytes < GC_MULT * heapsize) {
  816. #         ifdef DEBUG
  817.         printf("Calling gcollect\n");
  818. #         endif
  819.       gcollect();
  820.     } else {
  821.       expand_hp(NON_GC_HINCR);
  822.     }
  823.       }
  824.       if (aobjfreelist[sz] == ((struct obj *) 0)) {
  825.       new_hblk(-sz);
  826.       }
  827.     }
  828.     return(aobjfreelist[sz]);
  829. }
  830.  
  831. # ifdef SPARC
  832.   put_mark_stack_bottom(val)
  833.   long val;
  834.   {
  835.     mark_stack_bottom = (word *)val;
  836.   }
  837. # endif
  838.